import java.util.*;

/**
 * @author LKQ
 * @date 2022/3/9 11:21
 * @description 并查集
 * 通过并查集寻找附加的边。初始时，每个节点都属于不同的连通分量。
 * 遍历每一条边，判断这条边连接的两个顶点是否属于相同的连通分量.
 * 1、如果两个顶点属于不同的连通分量，则说明在遍历到当前的边之前，这两个顶点之间不连通，因此当前的边不会导致环出现，合并这两个顶点的连通分量。
 * 2、如果两个顶点属于相同的连通分量，则说明在遍历到当前的边之前，这两个顶点之间已经连通，因此当前的边导致环出现，为附加的边，将当前的边作为答案返回。

 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] ed = {{1,2}, {1,3}, {2,3}};
        solution.findRedundantConnection(ed);
    }
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        UnionFind unionFind = new UnionFind(n);
        for (int i = 0; i < n; i++) {
            int[] edge = edges[i];
            int node1 = edge[0], node2 = edge[1];
            if (unionFind.find(node1) != unionFind.find(node2)) {
                // 如果不在一个连同分量里面，那么合并
                unionFind.union(node1, node2);
            }else {
                // 找到相同的连通分量了，即附加的边
                return edge;
            }
        }
        return new int[0];
    }
}
